;; AScheme Example Programs
;; This file contains example Scheme programs to demonstrate the interpreter
;; These examples can be entered as multi-line expressions in the REPL

;; Basic arithmetic
(+ 1 2 3 4 5)                    ; => 15
(* 2 3 4)                        ; => 24
(/ 100 5 2)                      ; => 10
(- 20 5 3)                       ; => 12

;; Variable definition
(define pi 3.14159)
(define radius 5)
(define area (* pi (* radius radius)))
area                             ; => 78.53975

;; Simple functions using shorthand syntax
(define (square x) (* x x))
(square 7)                       ; => 49

(define (double x) (* 2 x))
(double 21)                      ; => 42

;; Equivalent lambda syntax for comparison
(define square-lambda (lambda (x) (* x x)))
(square-lambda 7)                ; => 49

;; Conditional expressions using shorthand syntax
(define (abs x) 
  (if (< x 0) 
      (- x) 
      x))
(abs -5)                         ; => 5
(abs 3)                          ; => 3

;; Recursive functions using shorthand syntax
(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))
(factorial 5)                    ; => 120

(define (fibonacci n)
  (if (< n 2)
      n
      (+ (fibonacci (- n 1)) 
         (fibonacci (- n 2)))))
(fibonacci 8)                    ; => 21

;; List operations
(define my-list (list 1 2 3 4 5))
my-list                          ; => (1 2 3 4 5)

(car my-list)                    ; => 1
(cdr my-list)                    ; => (2 3 4 5)
(cons 0 my-list)                 ; => (0 1 2 3 4 5)

;; Test pair? predicate
(pair? my-list)                  ; => #t (non-empty list is a pair)
(pair? (cons 1 2))               ; => #t (cons creates a pair)
(pair? '())                      ; => #f (empty list is not a pair)
(pair? 42)                       ; => #f (number is not a pair)
(pair? 'symbol)                  ; => #f (symbol is not a pair)

;; List length function (demonstrating multi-line formatting)
(define (length lst)
  (if (null? lst)
      0
      (+ 1 (length (cdr lst)))))
(length my-list)                 ; => 5

;; List sum function
(define (sum lst)
  (if (null? lst)
      0
      (+ (car lst) (sum (cdr lst)))))
(sum my-list)                    ; => 15

;; Higher-order functions
(define apply-twice (lambda (f x)
  (f (f x))))
(apply-twice square 3)           ; => 81

(define compose (lambda (f g)
  (lambda (x) (f (g x)))))
(define square-and-double (compose double square))
(square-and-double 4)            ; => 32

;; Map function (applies function to each element)
(define map (lambda (f lst)
  (if (null? lst)
      ()
      (cons (f (car lst)) 
            (map f (cdr lst))))))
(map square (list 1 2 3 4))      ; => (1 4 9 16)

;; Filter function
(define filter (lambda (pred lst)
  (cond
    ((null? lst) ())
    ((pred (car lst)) 
     (cons (car lst) (filter pred (cdr lst))))
    (else (filter pred (cdr lst))))))

(define is-even (lambda (x) (= (- x (* 2 (/ x 2))) 0)))
;; Note: This is a simplified even check since we don't have modulo

;; Append two lists
(define append (lambda (lst1 lst2)
  (if (null? lst1)
      lst2
      (cons (car lst1) (append (cdr lst1) lst2)))))
(append (list 1 2) (list 3 4))   ; => (1 2 3 4)

;; Reverse a list
(define reverse (lambda (lst)
  (define reverse-helper (lambda (lst acc)
    (if (null? lst)
        acc
        (reverse-helper (cdr lst) (cons (car lst) acc)))))
  (reverse-helper lst '())))
(reverse (list 1 2 3 4 5))       ; => (5 4 3 2 1)


(define reverse
  (lambda (lst)
    ;; Check if argument is a list
    (if (not (list? lst))
        (error "reverse: argument must be a list")
        (begin
          ;; Define helper function with accumulator for tail recursion
          (define reverse-helper
            (lambda (lst acc)
              (if (null? lst)
                  acc
                  (reverse-helper (cdr lst) (cons (car lst) acc)))))
          ;; Call helper with initial empty accumulator
          (reverse-helper lst '())))))

(define nil '())

(define (reverse l)
  (if (null? l)
     nil
     (append (reverse (cdr l)) (list (car l)))
  )
)


;; Find maximum in a list
(define max-list (lambda (lst)
  (if (null? (cdr lst))
      (car lst)
      (let ((rest-max (max-list (cdr lst))))
        (if (> (car lst) rest-max)
            (car lst)
            rest-max)))))
(max-list (list 3 7 2 9 1))      ; => 9


;; Greatest Common Divisor (Euclidean algorithm)
(define gcd (lambda (a b)
  (if (= b 0)
      a
      (gcd b (- a (* b (/ a b)))))))
;; Note: This is simplified since we don't have proper integer division

(gcd 24 18)

;; Power function
(define power (lambda (base exp)
  (if (= exp 0)
      1
      (if (= exp 1)
          base
          (* base (power base (- exp 1)))))))
(power 2 8)                      ; => 256

;; Let binding examples
(let ((x 10) (y 20))
  (+ x y))                       ; => 30

(let ((double (lambda (x) (* 2 x))))
  (double 15))                   ; => 30

;; Nested let
(let ((x 5))
  (let ((y (+ x 3)))
    (* x y)))                    ; => 40

;; TAIL CALL OPTIMIZATION EXAMPLES
;; These examples demonstrate tail-recursive functions that are optimized
;; to run in constant stack space, allowing for large recursion depths

;; Tail-recursive factorial (optimized)
(define (factorial-tail n acc)
  (if (= n 0)
      acc
      (factorial-tail (- n 1) (* n acc))))
(define (factorial-optimized n) (factorial-tail n 1))
(factorial-optimized 10)         ; => 3628800

;; Tail-recursive sum (optimized)
(define (sum-to-n-tail n acc)
  (if (= n 0)
      acc
      (sum-to-n-tail (- n 1) (+ acc n))))
(define (sum-to-n n) (sum-to-n-tail n 0))
(sum-to-n 100)                   ; => 5050

;; Tail-recursive countdown (can handle large numbers)
(define (countdown n)
  (if (= n 0)
      'done
      (countdown (- n 1))))
(countdown 1000)                 ; => done (without stack overflow!)

;; GCD and remainder examples using built-in remainder function
(remainder 100000 3)             ; => 1 (much faster than custom implementation)

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(gcd 24 18)                      ; => 6
